package Leetcode.Stack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Stack;

/**
 * @Author: kirito
 * @Date: 2024/4/13 17:25
 * @Description: 最大宽度坡
 * 中等
 * 相关标签
 * 相关企业
 * 给定一个整数数组 A，坡是元组 (i, j)，其中  i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。
 *
 * 找出 A 中的坡的最大宽度，如果不存在，返回 0 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：[6,0,8,2,1,5]
 * 输出：4
 * 解释：
 * 最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.
 * 示例 2：
 *
 * 输入：[9,8,1,0,1,9,4,0,4,1]
 * 输出：7
 * 解释：
 * 最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.
 *
 *
 * 提示：
 *
 * 2 <= A.length <= 50000
 * 0 <= A[i] <= 50000
 *
 *
 */

public class maxWidthRamp {
    public static void main(String[] args) {
        int[] nums = {6, 0, 8, 2, 1, 5};
        System.out.println(maxWidthRamp4(nums));
    }

    /**
     * 有点像之前慧策的那个132的和，但是这相比简单一点
     * 可以先右到左求出每个数最右边的最大值是多少，存一个数组temp
     * 然后遍历原数组求差值，取最大的差值返回
     * O(n)
     *
     * 好像理解错题意了，但是想法是好的 ^ ^
     * 不仅要大，而且尽可能远，这样坡会越来越宽
     *
     * 空间换时间？在用个map存当前值最右边最远的数？
     * @param nums
     * @return
     */
    public static int maxWidthRamp(int[] nums) {
        int len = nums.length;
        int[] temp = new int[len];
        temp[len - 1] = nums[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            if (nums[i] < temp[i + 1]) {
                temp[i] = temp[i + 1];
            }else{
                temp[i] = nums[i];
            }
        }
        int max = 0;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, temp[i] - nums[i]);
        }
        return max;
    }

    /**
     * 用栈的话第一个大的好找，但是他是要最远的 那个大的怎么用栈呢
     * @param nums
     * @return
     */
    public static int maxWidthRamp2(int[] nums) {
        int len = nums.length;
        int[] temp = new int[len];
        temp[len - 1] = nums[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            if (nums[i] < temp[i + 1]) {
                temp[i] = temp[i + 1];
            }else{
                temp[i] = nums[i];
            }
        }
        int max = 0;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, temp[i] - nums[i]);
        }
        return max;
    }

    public static int maxWidthRamp3(int[] A) {
        // 获取数组A的长度
        int N = A.length;

        // 创建一个与A相同长度的Integer数组B，用于存储索引
        Integer[] B = new Integer[N];
        for (int i = 0; i < N; ++i){
            B[i] = i; // 初始化B，使得B[i]等于i
        }

        // 对数组B进行排序，排序的依据是A数组中对应索引的值
        // 即B中的索引按照A中对应的值的大小进行排序
        Arrays.sort(B, (i, j) -> ((Integer) A[i]).compareTo(A[j]));

        // 初始化最宽坡度为0
        int ans = 0;

        // 初始化m为N，m用于记录当前遍历到的最小索引值
        int m = N;
        for (int i: B) {
            // 更新最宽坡度为当前索引i与m的差值的最大值
            ans = Math.max(ans, i - m);

            // 更新m为当前索引i与m的较小值
            m = Math.min(m, i);
        }

        // 返回最宽坡度
        return ans;
    }
    public static int maxWidthRamp4(int[] A) {
        Deque<Integer> stack=new ArrayDeque<>();
        int res=0;
        for(int i=0;i<A.length;i++){
            if(stack.isEmpty() || A[stack.peek()]>A[i]){
                stack.push(i);
            }
        }
        for(int i=A.length-1;i>=0;i--){
            while(!stack.isEmpty() && A[stack.peek()]<=A[i]){
                int cur=stack.pop();
                res=Math.max(res,i-cur);
            }
        }
        return res;
    }
    //画个图就理解思路了，方法很巧妙  递减入栈，保证其他书能和栈顶元素构成坡
    public int maxWidthRamp5(int[] nums) {
        int res = 0;
        int n = nums.length;
        Stack<Integer>min = new Stack<>();

        min.push(0);
        for(int i = 1; i < n; i ++){
            if(nums[i] < nums[min.peek()]){
                min.push(i);
            }
        }

        for(int i = n - 1; i >= 0; i --){
            while(!min.isEmpty() && nums[min.peek()] <= nums[i]){
                //先不pop。一直比较下去，最后pop
                res = Math.max(res,i - min.peek());
                min.pop();
            }
        }

        return res;
    }
}
